#include <iostream>
#include <queue>
using namespace std;
#define MVNum 1000//最大顶点数
int visited[MVNum]={0};//判别顶点是否被访问过
typedef struct ArcNode//边结点
{
    int adjvex; //该边所指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条边的指针
    //OtheInfo info;//边相关的信息（如权值）
}ArcNode;

typedef struct VNode//顶点信息
{ 
    int data;
    ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];//AdjList表示邻接表类型为VNode型数组

typedef struct//邻接表
{
    AdjList adjlist;
    int vexnum, arcnum; //图的当前顶点数和边数
}ALG;//邻接表

int LocateVex(ALG G, int v)//邻接表G中v的位置
{
    for(int i=1; i<=G.vexnum; i++)
    {
        if(G.adjlist[i].data == v)
           return i;
    }
    return -1;
}

void CreateDG(ALG &G)//邻接表表示法，创建 有向图G
{
    int i, j, k;
    cin >> G.vexnum >> G.arcnum;//输入图总顶点数和总边数
    for (i = 1; i <= G.vexnum; i++) // 输入各点，构建 邻接表头结点表,从1开始编号
    {
        G.adjlist[i].data = i;
        G.adjlist[i].firstarc = NULL; //指向第一条依附该顶点的边的指针,初始化为NULL
    }
    for (k = 0; k < G.arcnum; k++) // 输入各边，构建邻接表
    {
        int v1, v2;
        char ch;
        //cin >> v1 >> ch >> v2; // 输入一条边的两个顶点
        scanf("%d%c%d",&v1,&ch,&v2);
        i = LocateVex(G, v1);//确定v1和v2在G中位置i和j，即顶点在G.adjlist中的序号
        j = LocateVex(G, v2);
        ArcNode *p;
        p=new ArcNode;//生成一个新的边结点
        p->adjvex = j;//该边所指向的顶点的位置为j，即该边的邻接点序号为j
        p->nextarc = G.adjlist[i].firstarc;
        G.adjlist[i].firstarc = p;//头插法，把新的边结点插入插入顶点Vi的 邻接边表 的头部
    }
}

void CreateUDG(ALG &G)//邻接表表示法，创建 无向图G
{
    int i, k, temp;
    cin >> G.vexnum >> G.arcnum;//输入图总顶点数和总边数
    for (i = 1; i <= G.vexnum; i++) // 输入各点，构建 邻接表头结点表,从1开始编号
    {
        cin >> temp;
        G.adjlist[i].data = temp;
        G.adjlist[i].firstarc = NULL; //指向第一条依附该顶点的边的指针,初始化为NULL
    }
    for (k = 0; k < G.arcnum; k++) // 输入各边，构建邻接表
    {
        int v1, v2;
        //char ch;
        //cin >> v1 >> ch >> v2; // 输入一条边的两个顶点
        scanf("%d%d",&v1,&v2);
        int i, j;
        i = LocateVex(G, v1);//确定v1和v2在G中位置i和j，即顶点在G.adjlist中的序号
        j = LocateVex(G, v2);
        ArcNode *p1,*p2;
        p1=new ArcNode;//生成一个新的边结点
        p1->adjvex = j;//该边所指向的顶点的位置为j，即该边的邻接点序号为j
        p1->nextarc = G.adjlist[i].firstarc;
        G.adjlist[i].firstarc = p1;//头插法，把新的边结点插入插入顶点Vi的 邻接边表 的头部
        p2=new ArcNode;//生成一个新的边结点
        p2->adjvex=i;//该边所指向的顶点的位置为i，即该边的邻接点序号为i
        p2->nextarc = G.adjlist[j].firstarc;
        G.adjlist[j].firstarc = p2;//头插法，把新的边结点插入插入顶点Vj的 邻接边表 的头部
    }
}

void DFSAL(ALG G,int v)//深度优先遍历 邻接表 储存的图，从第v个顶点开始
{
  //  cout << v;//输出被访问顶点的编号（位置）
    visited[v] = 1;//标记被访问的点
    ArcNode *p;
    p = G.adjlist[v].firstarc;//p为第v个顶点的第一条邻接边
    while(p!=NULL)
    {
        if(visited[p->adjvex]==0)//p->adjvex为第v个顶点的第一条邻接边指向的顶点的位置，即第v个顶点相邻顶点的位置。没有被访问
        {
           DFSAL(G, p->adjvex);//递归遍历
        }
        p = p->nextarc;//p移到下一个边结点
    }
}

void BFSAL(ALG G,int v)//广度优先遍历 邻接表 储存的图，从第v个顶点开始
{
    int i;
    queue<int> Q;//队列辅助遍历，不用递归
    ArcNode *p;
    for (i = 1; i <= G.vexnum; i++)
    {
        visited[i] = 0;//初始化访问数组为0
    }
    cout << 'v'<<G.adjlist[v].data<<' ';//输出被访问顶点
    visited[v] = 1;//标记被访问的点
    Q.push(v);//顶点的编号入队
    while(!Q.empty())//队列不为空
    {
        p =G.adjlist[Q.front()].firstarc;//与队首编号顶点邻接的第一条边
        Q.pop();//队首出队
        while(p!=NULL)
        {
            if(visited[p->adjvex]==0)//与队首顶点相邻顶点未被访问
            {
                cout << 'v' << G.adjlist[p->adjvex].data << ' '; // 输出被访问顶点
                visited[p->adjvex] = 1;//标记被访问的点
                Q.push(p->adjvex);//该顶点入队
            }
            p = p->nextarc;//下一个边结点，找下一个结点
        }
    }
}

int DFSroad(ALG G, int i, int j)//DFS判断顶点vi,vj之间有无路径
{
    int k;
    for (k = 1; k <= G.vexnum; k++)
    {
        visited[k] = 0;//初始化访问数组为0
    }
    DFSAL(G, i);//从i开始深度遍历
    if(visited[j]==0)//从i开始没有访问到j
        return 0;
    else
        return 1;
}

int BFSroad(ALG G, int i, int j)//BFS判断顶点vi,vj之间有无路径
{
    int k;
    for (k = 1; k <= G.vexnum; k++)
    {
        visited[k] = 0;//初始化访问数组为0
    }
    BFSAL(G, i);//从i开始广度遍历
    if(visited[j]==0)//从i开始没有访问到j
        return 0;
    else
        return 1;
}

int main()
{
    ALG G;
    CreateUDG(G);
    BFSAL(G,1);
    return 0;
}